perm filename PLNR.BGB[S,DOC] blob
sn#166185 filedate 1974-05-22 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00040 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00006 00002 SAILON NUMBER 67 MICRO PLANNER MANUAL
C00008 00003 INTRODUCTION PAGE 2
C00012 00004 MEMORY STRUCTURE - INTRODUCTION. PAGE 3
C00014 00005 MEMORY STRUCTURE - ASSERTIONS. PAGE 4
C00018 00006 PAGE 5
C00021 00007 0!*(THSETQ (THV X) @WHITE) give x a plnr value. PAGE 6
C00024 00008 MEMORY STRUCTURE - PATTERNS. PAGE 7
C00028 00009 MEMORY STRUCTURE - PATTERNS - continued. PAGE 8
C00030 00010 MEMORY STRUCTURE - THEOREMS. PAGE 9
C00033 00011 CALL-BY-PATTERN - Goal Direction. PAGE 10
C00038 00012 FILTERING PAGE 11
C00041 00013 MEMORY STRUCTURE - PATTERN MATCHING. PAGE 12
C00045 00014 A Second Explanation of Pattern-Matching: PAGE 13
C00049 00015 MEMORY STRUCTURE - ASSERTION & THEOREM PATTERN STORAGE. PAGE 14
C00053 00016 ASSERTION & THEOREM STORAGE - continued. PAGE 15
C00056 00017 MEMORY SIZE PAGE 16
C00060 00018 MEMORY STRUCTURE - PLANS, ACTIONS and WORLDS. PAGE 17
C00063 00019 II. CONTROL STRUCTURE PAGE 18
C00068 00020 CONTROL STRUCTURE - PROGRAMS & STEPS. PAGE 19
C00073 00021 CONTROL STRUCTURE - PLNR PROCESSOR STATE. PAGE 20
C00078 00022 CONTROL STRUCTURE - THTREE. PAGE 21
C00081 00023 CONTROL STRUCTURE - THTREE - continued. PAGE 22
C00085 00024 CONTROL STRUCTURE - THTREE - continued. PAGE 23
C00089 00025 CONTROL STRUCTURE - THE PLNR INTERPRETER. PAGE 24
C00094 00026 CONTROL STRUCTURE - THE PLNR INTERPRETER - continued. PAGE 25
C00097 00027 A SUMMARY OF THE 35 PLNR PRIMITIVES. PAGE 26
C00101 00028 SIX VALUE PRIMITIVES PAGE 27
C00105 00029 SIX THEOREM PRIMITIVES PAGE 28
C00110 00030 SIX THEOREM PRIMITIVES - continued. PAGE 29
C00113 00031 SIX THEOREM PRIMITIVES - continued. PAGE 30
C00116 00032 EIGHT PROG PRIMITIVES PAGE 31
C00120 00033 EIGHT PROG PRIMITIVES - continued. PAGE 32
C00124 00034 EIGHT PROG PRIMITIVES - continued. PAGE 33
C00127 00035 FIVE BOOL PRIMITIVES PAGE 34
C00130 00036 FOUR IO PRIMITIVES PAGE 35
C00133 00037 (SETQ MONKEY @(THGOAL (MONKEY GETS BANANAS)(THTBF THTRUE))) PAGE 36
C00136 00038 (DEFPROP CLIMB (THANTE (X Y Z W S Q) (MONKEY AT (THV X)) PAGE 37
C00139 00039 PLNR ERROR MESSAGES explanation PAGE 38
C00142 00040 GLOSSARY and INDEX PAGE 39
C00145 ENDMK
C⊗;
SAILON NUMBER 67 MICRO PLANNER MANUAL
STANFORD ARTIFICIAL INTELLIGENCE LABORATORY APRIL 1972
OPERATING NOTE NUMBER 67
MICRO PLANNER ALTERNATE REFERENCE MANUAL
Bruce g. Baumgart
ABSTRACT:
Micro Planner, a program written in LISP, is described in
terms of its associative memory structure and its backtracking
control structure.
CONTENTS:
INTRODUCTION.
I. MEMORY STRUCTURE.
1. ASSERTIONS & VALUES.
2. PATTERNS.
3. THEOREMS.
4. PATTERN MATCHING.
4A. Pattern Accessing.
4B. Pattern Binding.
5. ASSERTION & THEOREM-PATTERN STORAGE.
6. PLANS.
II. CONTROL STRUCTURE.
1. PROGRAMS & STEPS.
2. PROCESSOR STATE.
3. THTREE & TREE NODES.
4. THE PLNR INTERPRETER.
III. PRIMITIVES.
1. VALUE PRIMITIVES.
2. THEOREM PRIMITIVES.
3. PROG PRIMITIVES.
4. BOOL PRIMITIVES.
5. IO PRIMITIVES.
6. LISPISH PRIMITIVES.
IV. EXAMPLE - Orban's Monkey.
INTRODUCTION PAGE 2
Micro Planner, PLNR, is a MIT MAC-AI implementation of a
subset of Carl Hewitt's robot language named PLANNER. PLNR was
written by Gerald Jay Sussman, Terry Winograd and Eugene Charniak.
The Stanford AI SYS: copy of PLNR is named PLNR and is
obtained by typing "R PLNR" at monitor level; PLNR will self
initialize and allocate its LISP image and will then enter its
READ-THVAL-PRINT loop. PLNR types an integer, exclamation point and
an asterisk before waiting for user teletype input; typing (THDO)
carriage return will return value T and assure you that PLNR is alive
and well and listening. External files of PLNR code can be loaded by
typing (UREAD filename). LISP level can be obtained by typing T until
only asterisks rather than !*'s appear; PLNR level can be obtained by
executing (THINIT) at lisp level.
All user questions, suggestions, or comments about PLNR
should be directed to Richard Orban, RPO, who is maintaining the
current version of PLNR; however errors in this manual should be
brought to the attention of Bruce Baumgart, BGB. A knowledge of LISP
and of the Stanford AI time sharing system is a prerequiste to using
PLNR.
Finally, one might expect a reference manual introduction to
state clearly what PLNR is good for; it is alleged that PLNR can
derive simple plans and syllogisms from its associative data base of
assertions and theorems; and that PLNR interprets a programming
language; and that PLNR is a question answering system and a theorem
prover. It has been said that PLNR provides a good representation for
knowledge; and Winograd used PLNR to implement a portion of his
simulated robot, SHRDLU. PLNR's theoretical value lies in that it
illustrates one significantly new programming idea, subroutine call
by pattern also referred to as goal directed theorems; three other
major ideas that PLNR ilustrates are backtrack intrepreting,
associative memory and pattern matching.
ACKNOWLEDGEMENT
Parts I and II of this manual are my own; part IV is a PLNR
program written by Richard Orban; and part III is an adulterated copy
of the second part of the original PLNR manual of Sussman and
Winograd; that is part III contains unquoted excerpts from the
original authors. - BGB.
MEMORY STRUCTURE - INTRODUCTION. PAGE 3
The bulk of PLNR is an associative memory of assertions and
theorem patterns combined with a pushdown memory of variable
bindings. Also PLNR subsumes the LISP memory structures of values and
property lists. Thus in all, PLNR consists of four major memory
systems:
MEMORY SYSTEM STORE FETCH
i. PLNR Values THSETQ THV
ii. PLNR Assertions THASSERT THGOAL
iii. LISP Values SETQ EVAL
iv. LISP Properties PUTPROP GET
As in LISP, PLNR assigns values to variables by binding when
functions are called; and as in LEAP, PLNR assigns values to
variables by binding when the associative data base is searched.
However, unique to PLNR, is that the dictinction between an
associative memory reference and a subroutine call is concealed; it
is the theme of this alternate reference manual to emphasize what is
memory and what is process; but it is PLNR's best trick to make
process look like memory.
MEMORY STRUCTURE - ASSERTIONS. PAGE 4
Assertions are ordered n-tuples represented by lists of
non-numeric objects called items. A good deal can be asserted using
only pairs and triples in formats such as:
(property object) (HEAVY BLOCK)
(name value) (LOCUS20 (200 10 -12))
(relation object1 object2) (ABOVE BLK1 BLK2)
(attribute object value) (COLOR BLK1 RED)
(type name) (INTEGER X)
The items of an assertion are either non-numeric LISP atoms
or arbitrary list structure, in either event the items of an
assertion are always interpreted as being constants (or that is as
ground instances, from a predicate calculus point of view).
As an associative memory system, PLNR can store assertions
and retrieve sets of them that satisfy partial item specifications.
ASSERTION STORE PRIMITIVE: (THASSERT assertion)
examples: (THASSERT (ROSES ARE RED))
(THASSERT (VIOLETS ARE BLUE))
(THASSERT (VIOLETS ARE PURPLE))
(THASSERT (SUGAR IS SWEET ))
ASSERTION FETCH PRIMITIVE: (THGOAL assertion)
(THGOAL (VIOLETS ARE BLUE))
(THGOAL (ROSES ARE ?))
(THGOAL ( ? IS SWEET))
(THGOAL (VIOLETS ARE BLACK))
ASSERTION ERASE PRIMITIVE: (THERASE assertion);
(THERASE (ROSES ARE RED))
THASSERT puts assertions into the PLNR's associative data
base. A THASSERT is analogous to a declarative statement and the
given assertion is accepted with no interpretation of its content,
validity, or its consistency with earlier statements. THGOAL asks
whether an assertion is in the associative memory. A THGOAL is
analogous to a question; if the assertion is present than it is
returned; if the assertion is not in the associative memory then NIL
is returned.
THASSERT and THGOAL with question marks, as illustrated
above, amount to a simple fill in the blank question answering
system, where the question mark character, "?", is used for the
blank. Other notations for "filling in the blank" are (THV X)
and (THNV X) instead of a question mark; these notations bind the
value that goes in the blank to the variable X. Now the variable X
might already have had a value; so in that event a (THNV X) variable
will readily give up its earlier value in order to get a new one;
while a (THV X) variable will insist that an assertion be found that
matches its current value; however a (THV X) variable will take a new
PAGE 5
value when its previous value was THUNASSIGNED. A possible PLNR
dialogue in caps is on the left, comments are in lower case and on
the right:
0!*(THASSERT(ROSES ARE RED)) human inputs after !* 's
((ROSES ARE RED)) the assertion returns in a list
0!*(THSETQ(THV X) @RED)
RED
0!*(THSETQ(THNV Y) @BLACK)
BLACK
0!*(THSETQ(THV Z) @THUNASSIGNED) declare varname z
THUNASSIGNED
0!*(THGOAL (ROSES ARE (THV X))) indeed, roses are red.
((ROSES ARE RED))
0!*(THGOAL (ROSES ARE (THV Y))) thv y sticks to its
NIL black value, roses
aren't black
0!*(THV Y)
BLACK
0!*(THGOAL (ROSES ARE (THNV Y))) but thnv y gives up
((ROSES ARE RED)) black and becomes red.
0!*(THNV Y)
RED
0!*(THGOAL (ROSES ARE (THV Z))) and thv z unassigned
((ROSES ARE RED)) also turns red.
0!*(THV Z)
RED
The above discourse also introduces the PLNR value primitives
THSETQ, THV and THNV; THSETQ is a memory store operation; THV and
THNV are memory fetch operations. PLNR values are kept in a list
which is named THALIST; whereas LISP values are kept in atom property
lists. The following PLNR dialogue illustrates the LISP and PLNR
double valued memory structure; and foreshadows the notion of value
backtracking under the functions THERT and THPROG:
0!*(SETQ X @RED) give x an old lisp value, so
RED plnr can get an old value.
0!*(THSETQ X @RED) give x a new lisp value.
RED
0!*(THSETQ (THV X) @WHITE) give x a plnr value. PAGE 6
WHITE
0!*X and behold the lisp value
RED is still there.
0!*(THV X) and the plnr value
WHITE is still there
0!*THALIST
((NIL NIL)(X WHITE))
0!*(THPROG()(THSETQ X @BROWN (THV X) @GRAY)(THERT))
>>> go down a level and reset
LISTENING the lisp and plnr values
1!*X of the variable x.
BROWN see, the lisp x turned brown.
1!*(THV X) see, the plnr x turned gray.
GRAY
1!*THALIST
((NIL NIL)(X GRAY))
1!*NIL this exits the prog's thert.
NIL
0!*X and thru the magic of backtracking
RED lisp x regains its red hue.
0!*(THV X) and plnr x regains its whiteness.
WHITE
Finally, an example of THRESTRICT. As a stand alone primitive
(THRESTRICT varname filters...) splices the given list of filter
functions into the THALIST on given variable's (varname value) pair;
which then leaves a (name value filters) "pair" in the THALIST. A
filter is a function of a single variable that returns non-NIL if its
argument passes thru the filter.
(DEFPROP PATRIOTIC (X) (MEMQ X @(RED WHITE BLUE)))
(THSETQ (THV X) @UNASSIGNED)
(THASSERT (ROSES ARE RED))
(THASSERT (ROSES ARE YELLOW))
(THASSERT (ROSES ARE FLOWERS))
(THRESTRICT (THV X) PATRIOTIC)
(THGOAL (ROSES ARE (THV X)))
Yields (THV X) assigned to the value RED rather than YELLOW or
FLOWERS.
MEMORY STRUCTURE - PATTERNS. PAGE 7
In PLNR assertions with variables do not exist; rather a
distinct entity which is called a "pattern" is stored and fetched
using the theorem structures. Patterns subsume assertions in that a
pattern doesn't have to have a variable, however a constant pattern
is not quite an assertion, since patterns in PLNR have the two roles
of theorem calling addresses and of argument binding lists which PLNR
assertions lack.
In this section, the structure and a terminology of PLNR
patterns is introduced. The semantics of patterns will be explained
in the subsequent sections on theorems and pattern-matching. The
structure of a PLNR pattern is captured by the following BNF:
pattern ← (itemexprs...)
pattern ← (THEV expr )
itemexpr ← ?
itemexpr ← item
itemexpr ← itemvar
itemexpr ← listitem
itemexpr ← (THEV expr )
itemexpr ← (THRESTRICT itemvar filters)
itemexpr ← (THRESTRICT ? filters)
itemvar ← (THV varname) or ?varname
itemvar ← (THNV varname) or ←varname
The above BNF means that a pattern is a list of item
expressions or a (THEV expression) which THVAL's to a pattern. An
item expression is one of six things; it is either a lone question
mark character, or an item itself, or it's an item variable or it's a
list item itself or it's (THEV expression) which THVAL's to an
itemexpr or it's a THRESTRICT kludge.
Next, there are two distinct kinds of variable occurences in
PLNR, THV and THNV. Now a variable mentioned within some context is
either unassigned, unbound or has a value. A bound THV variable can
only match to its values whereas a bound THNV variable will give up
its current value and assume another in order to match. Finally,
"item" is any non-numeric LISP atom except NIL. "listitem" is a LISP
list. "expr" as used above had better THVAL to a pattern or itemexpr
respectively.
In PLNR code from MIT, THπ and THNV are often abbreviated to
dollar-sign-question-mark and dollar-sign-left-arrow prefixes
respectively, that is (THV x)≡$?x and (THNV x)≡$←x; Stanford PLNR
will soon have ? and ← prefix characters for quoting variables.
MEMORY STRUCTURE - PATTERNS - continued. PAGE 8
Patterns in PLNR serve in two roles, first patterns are used
for addressing theorems and second patterns are used for binding
theorem parameters. Like an ALGOL procedure, the formal parameters of
a theorem can be arguments, results or both; and can be
"bound-by-value" or "bound-by-name".
In their first role, theorem addressing, patterns like
addresses in any memory system, appear as keys and as tags. Address
tags are attached to memory containers and when a process desires the
contents of some memory containers it calls out an address key. The
memory then takes the calling key and finds the containers with tags
that correspond to that key, and returns the contents of those
containers to the process. All of this is by way of introducing two
new words into PLNR; which are "calling-pattern-key" and
"theorem-pattern-tag". These two halves of the pattern as an address
notion are quite important.
Patterns in their second role, specify the parameter binding
of theorems. (see pattern-binding on page 13).
MEMORY STRUCTURE - THEOREMS. PAGE 9
In PLNR the entities called "theorems" are like subroutines,
the facts about theorems in outline form are:
There are three kinds of theorems:
THCONSE consequent theorems.
THANTE antecedent theorems.
THERASING erasing theorems.
Theorems are defined by:
(DEFPROP name body THEOREM)
body is (indicator varlist pattern-tag steps...)
indicator is THCONSE, THANTE or THERASING
Theorem Formats:
(DEFPROP theorem1
(THCONSE varlist consequent steps...) THEOREM)
(DEFPROP theorem2
(THANTE varlist antecedent steps...) THEOREM)
(DEFPROP theorem3
(THERASING varlist antecedent steps...) THEOREM)
Theorems are placed in (or out) of the theorem base by:
(THASSERT name) or (THASSERT name (THPROP expr))
(THERASE name)
(THDATA)
There are four theorem calling primitives:
i.) (THGOAL pattern-key recommendations...)
ii.) (THASSERT pattern-key recommendations...)
iii.) (THERASE pattern-key recommendations...)
iv.) (THAPPLY theorem assertion)
When a theorem is called by pattern:
i.) The theorem's varlist is bound.
ii.) The calling-pattern-key (bound under the old THOLIST) and
the theorem-pattern-tag (bound under the new THALIST) are
pattern-matched; which can bind theorem variables by
value to constants and can bind theorem variables
by name to calling pattern variables.
iii.) IF the match wins,
THEN the theorem is executed as a THPROG,
ELSE all bindings are undone
and the theorem isn`t entered.
iv.) Eventually the theorem should finish its execution;
THANTE and THERASING theorems can not return a value
and are assumed to succeed; THCONSE theorems either
explicitly return a value indicating success or
failure or a THCONSE theorem may just SUCCEEDs
and its theorem-tag-pattern with bound variables
evaluated is returned as its result value.
CALL-BY-PATTERN - Goal Direction. PAGE 10
The PLNR subroutine calling mechanism in THASSERT, THGOAL,
and THERASE is a "call by pattern". The idea is that rather
than calling a subroutine by its name as is done in FORTRAN, ALGOL
and LISP; PLNR requires theorem subroutines to have an additional
declaration, namely a pattern-tag, so that a subroutine call need
only mention a pattern-key. Thus the PLNR subroutine calling
mechanism passes control to the zero, one or several subroutines with
a pattern-tag corresponding to the pattern-key being called.
And in particular, when a THCONSE theorem is called and when
that theorem succeeds but does not return an explicit value then the
THCONSE theorem's pattern tag with bound variables evaluated is
returned as the result of the call by pattern; this particular
theorem calling mode is PLNR's intellectual centerpiece and is know
as a goal directed theorem call.
KINDS-OF-THEOREMS
There are three kinds of theorems THANTE, THCONSE and
THERASING corresponding to the three basic associative memory
operations store, fetch and erase; which are called assert, goal and
erase in PLNR. The three kinds of theorems differ only in their
calling conventions and not in their content, which is in fact any
legal thprog list of executable steps. The calling conventions are
that THANTEs are called by the THASSERT primitive, THCONSEs are
called by the THGOAL primitive and THERASErs are called by the
THERASE primitive; and that THANTEs and THERASErs can only return
their results by side effect, whereas a THCONSE (being the analog of
a memory fetch) can return a value. Furthermore, THASSERT and THERASE
call all their possible theorems at once whereas a THGOAL calls only
one of its theorems at first and saves the names of the others for
latter "trys" in case of a failure.
ORDER-OF-EVENTS
The memory-theorem primitives are THASSERT, THGOAL and
THERASE; when such a primitive is called there are potentially six
events which occur in the following order:
1. assertion accessing.
2. theorem pattern accessing.
3. filtering.
4. theorem varlist binding.
5. pattern binding.
6. theorem thprog execution.
Now event 1 was discussed earlier in the section on assertions, and
events 2 and 5 are pattern-matching discussed in that section, and
events 4 and 6 are explained in part II which is about thprogs; which
leaves filtering to be explained.
FILTERING PAGE 11
A filter in PLNR is a LISP function of one argument which
evaluates non-NIL to indicate that its argument passes thru the
filter. There are three kinds of filters: Restrict filters, Assertion
Filters, and Theorem Filters. The argument passed to a restrict
filter is an object that PLNR wishes to bind to a restricted
variable; the argument passed to an assertion filter is the assertion
itself cons'ed to its given THPROP expr, so that the filter function
can look at CAR of its argument to see the assertion and CDR of its
argument to see that assertion's THPROP expr. Finally the argument
passed to a theorem filter is the name of the theorem that is about
to be tried, the THPROP's of that theorem can be inspected by GET'ing
them in the conventional LISP manner. The always true filter is
supplied by PLNR as THTRUE.
VARLIST-BINDING
A varlist is a list of varnames, (varname value)s or (varname
value restriction-filters). When the varlist is bound all the
variables are placed on the THALIST. Variables without initial values
are given the value THUNASSIGNED by default. Observe that a varname
is the actual atomic name of a PLNR variable and not (THV varname) or
(THNV varname).
MEMORY STRUCTURE - PATTERN MATCHING. PAGE 12
Pattern-matching is a two step memory process consisting of
pattern-accessing and pattern-binding; where pattern-accessing
consists of assertion-pattern accessing and theorem-pattern
accessing; and where pattern-binding consists of item comparison and
variable binding. And incidentally there are six kinds of itemexprs
and two kinds of variables and two kinds of bindings as well as two
pair of Ying-Yang notions BOUND-UNBOUND and ASSIGNED-UNASSIGNED. Or
in outline:
pattern-accessing
assertion-pattern accessing from the data base
theorem-pattern accessing from the theorem base
pattern-binding
item-comparison
itemvar-binding
bind-by-value
bind-by-name
A First Explanation of Pattern-Matching:
The pattern matcher in PLNR only matches patterns one level
deep. There are two distinct kinds of variable occurrences in PLNR
patterns, THV and THNV; THV are stronger than THNV in the sense that
THV variables hold on to their assigned values come hell or high
water, whereas THNV variables meekly give up their values in order to
conform to any constant item or assigned THV that comes along; when
two THNV are matched, the theorem pattern tag THNV wins. A pattern
item (or the entire pattern) may be of the form (THEV expr), which
means that the item (or pattern) is to be replaced with the result of
THVALuating the expression with the correct THALIST; (well during
a match the key is under its alist called the THOLIST and the tag is
under the alist resulting from binding the theorems varlist which is
called the THALIST). Finally, when theorem pattern tag variables
(THNV and unassigned THV) are bound to calling pattern key variables;
they are bound by name such that changing the value of the theorem
pattern tag variable will change the value of the calling pattern key
variable, even tho a constant argument might have been passed into
the theorem thru that variable, a different result value can be
passed out of the theorem thru that same variable; this is refered to
as being able to coerce your variables, or as parameter binding by
name or as parameter call by reference; however it is clearly an
asymetry in the pattern matching process and is one reason why
pattern matching isn't quite like the unification of a resolution
theorem prover.
A Second Explanation of Pattern-Matching: PAGE 13
pattern-accessing
THASSERT, THERASE and THGOAL all call the same pattern
accessing subroutine name THMATCHLIST(key,kind); THMATCHLIST's `key'
argument must be a pattern key and its `kind' argument must be either
THASSERTION, THCONSE, THANTE or THERASING. THMATCHLIST then cdr's
thru the key looking for atomic items and variables; on variables
THMATCHLIST assumes the item THVRB; on an item THMATCHLIST gets its
`kind' of bucket and then ASSOC's thru the bucket to get a list of
patterns or theorem names that have this particular item occurring at
this particular place in patterns of this particular length; (there
is no hash address calculations in the conventional sense, but merely
property list ASSOC scanning in the traditional LISP fashion.)
THMATCHLIST returns the smallest such list of patterns or theorem
names. THASSERT, THERASE and THGOAL make at most two calls on
THMATCHLIST - the first call is for THASSERTIONs (unless recommended
otherwise by THPSEUDO or THNODB) and the second is for THANTE,
THERASING or THCONSE theorems respectively (when theorem
recommendations or filters are present).
pattern-binding
If the tag and the key patterns are the same length after any
necessary THEV calls, the subroutine THMATCH1 mapc's the patterns
item by item thru the subroutine THMATCH2. Starting from the top,
THMATCH2 is an item-comparison for one of three cases:
i. question marks match anything.
ii. constant-constant case must match equal.
iii. variable anything case must match after
suitable binding and checking of restriction filters.
The variable-anything case consists of several subcases and details.
Two assigned THV variables must match equal; a THNV or unassigned THV
matchs anything by insisting that it take on the value of that
anything, where that value must pass all the restricts that may be on
that variable's THALIST pair; And involves RPLACA'ing the THALIST so
that a theorem variable points at what its corresponding calling
variable points at, thus effecting the binding by name mechanism
(except assigned THV variables in the theorem pattern, aren't bound
by name). A final detail of THMATCH2 involves handling THRESTRICTs
that are mentioned in the pattern, as well as the (THRESTRICT ?
filters...) kludge.
MEMORY STRUCTURE - ASSERTION & THEOREM PATTERN STORAGE. PAGE 14
Assertions and patterns are stored on the property lists of
items in a list of buckets of buckets of buckets of an assertion or
in a list of buckets of buckets of theorem names. Thus in effect,
each item points to all the assertions and theorems in which it
appears.
Itemvar occurences are stored on the global atom named THVRB,
just as if THVRB were an item at each variable occurences. Numbers,
list items and items that have been DEFPROP'ed T under the property
NOHASH do not point at the assertions and the theorems in which they
have appeared.
Assertion Bucket or Theorem Name.
At the bottom of the memory structure is either a theorem
name or an assertion in a bucket. An assertion in a bucket is merely
the assertion itself cons'ed to NIL; or it is the assertion itself
cons'ed to something that is alleged to be a "property" of that
assertion and was provided for by the THPROP recommendation when that
assertion was THASSERT'ed.
Assertion Bucket Examples:
(THASSERT (HUMAN TURING)) yields the assertion bucket
((HUMAN TURING)) which appears within the property of the items
HUMAN and TURING under the indicator THASSERTION.
(THASSERT (COLUMBUS DISCOVERS AMERICA) (THPROP 1492))
yields the assertion bucket ((COLUMBUS DISCOVERS AMERICA). 1492)
under the items AMERICA, COLUMBUS and DISCOVERS.
Length and Count Bucket.
Next up from the bottom, all the assertion buckets or all the
theorem names which have assertions or patterns of a certain length
and which have an occurence of a certain item at the same position
within their assertions or patterns are on a list which is prefixed
with two integers. The first integer is the length of the assertions
or patterns, and the second integer is the count of the assertion
buckets or theorem names in this list. The whole thing is then called
a Length and Count Bucket, say LCB, and (CAR LCB) is the length;
(CADR LCB) is the count; and (CDDR LCB) is a list of assertions
buckets or a list of theorem names.
Length and Count Bucket Example:
(THASSERT(HUMAN TURING))
(THASSERT(HUMAN PLATO))
(THASSERT(HUMAN MINSKY))
yields the LCB (2 3((HUMAN TURING))((HUMAN PLATO))((HUMAN MINSKY)))
under the item HUMAN.
ASSERTION & THEOREM STORAGE - continued. PAGE 15
Occurence Position Bucket
Next up comes the Occurence Position Bucket, OPB, which is
merely a list of Length and Count Buckets all of which have a certain
item occuring in the same position; prefixed with an integer which is
the occurence position of that item. And saying it another way, (CAR
OPB) is the occurence position and (CDR OPB) is a list of LCB's with
the item occuring in that position.
Bucket List.
Finally, all the Occurence Position Buckets are kept sorted
into one of four possible bucket lists depending on whether the
occurence came from an assertion or from one of the three kinds of
theorems. And a bucket list is merely a list of OPB's with a NIL
CONS'ed on the front. Bucket Lists are then DEFPROPed under the
appropriate indicator (THASSERTION,, THCONSE, THANTE or THERASING) on
the property list of each item involved in all assertions and theorem
patterns.
EXAMPLE
(THASSERT (HUMAN TURING)) results in
bucket-list-of-an-item gotten by (CDR(GET @HUMAN @THASSERTION)).
|
| occurence-position-bucket
| |
| | length-count-bucket
| | |
| | | assertion-bucket.
↓ ↓ ↓ ↓
( (1 (2 1 ( (HUMAN TURING) ) ) ) )
↑ ↑ ↑
| | count of the number of assertion buckets in this OPB.
| |
| length of the assertions in this bucket.
|
position of the item HUMAN in this bucket's assertions.
And (CDR(GET @TURING @THASSERTION)) yields the similar:
((2(2 1((HUMAN TURING)))))
MEMORY SIZE PAGE 16
The assertion (HUMAN TURING) requires 36 (decimal) words of
PDP-10 memory. The breakdown is as follows, 8 words for the atom
HUMAN and 10 words for the atom TURING and 16 words for two copies of
similar bucket list structure using INUM's and 2 words for the
assertion itself (HUMAN TURING).
The breakdown of a LISP atom is a word on the OBLIST, an atom
head word, 2 words per entry on the property list and finally 2*N
words for the PNAME ascii list and its full words. A PLNR item will
always have a PNAME and at least one THASSERTION, THCONSE, THANTE or
THERASING on its property list.
Assuming that a vocabulary of items has been established and
that each item has already aquired an adequate bucket structure, the
asymptotic memory cost for adding a new assertion is two times the
length of the assertion plus one, namely it is the cost of the
assertion itself and a pointer to it from every one of its item
occurences, and one more word for a NIL THPROP.
Restricting PLNR to two and three item assertions yields an
ITEM cost of 3 double word buckets each having 2 triple word buckets
with 10 words for ITEM atoms and bucket list header, which would come
to a cost as high as 46 words for an item that appears in all three
positions of a triple. To as low as 14 words for an item that only
appears in one position of a triple. In either event, 14 or 46 times
4096 items will blow core with no room for the assertions which cost
6 words each.
Experimentally, a 76K core image of PLNR starts out with
approximately 42 thousands words on its free list. A fresh triple of
three new INTERN'ed GENSYM'ed items costs exactly 50 words of free
storage, consquently 840 such triples involving 2520 items should
exhaust free storage, and it does.
MEMORY SPEED
A clean copy of compiled PLNR, takes about 10 milliseconds
to fetch (TURING IS HUMAN).
MEMORY STRUCTURE - PLANS, ACTIONS and WORLDS. PAGE 17
For a naive start, lets say that a plan is a sequence of
actions, an action changes the state of the world, and the world is
something that has states that can be changed.
For example, a computer program, a theorem proof or an
itinerary may be construed as a plan that could be constructed by
PLANNER. Planning involves a world and a model of that world, and
when planning is done by computer, the world might be simulated and
the model might be in the same notation.
As might be supposed, PLNR is a program for making plans.
Mysteriously PLNR has no particular representation for a plan nor
were plans ever mentioned in the original PLNR documentation. Thus it
is the responsibility of the user to define a particular
representation of a plan as well as to define the actions of which
the plan consists as well as to define the world in which the actions
of the plan might be executed.
It is important to realize, before starting, that the key
elements of PLNR must be provided by the user and that what PLNR
provides is a set of functions for manipulating those elements.
For example, Winograd's famous robot SHRDLU has only three
actions (GRASP object), (UNGRASP) and (MOVETO x y z); and a SHRDLU
plan consists of a list of these actions; and SHRDLU's world consists
of afew LISP atoms each with the ten properties: name, 3D locus,
color, object-type (BLOCK, PYRAMID or BOX), shape (POINTED or
RECTANGULAR), size (dx,dy,dz), support and on.
II. CONTROL STRUCTURE PAGE 18
0. INTRODUCTION
1. PROGRAMS & STEPS
2. PROCESSOR STATE
3. THTREE & TREE NODES
4. THE INTERPRETER
CONTROL STRUCTURE - INTRODUCTION.
The PLNR control structure is a backtrack stack interpreter;
such a structure consists of a program representation, a processor
state, a processor and a push down stack of all previous states the
processor has been thru since the beginning of a particular
computation. This total history of the processor states allows the
interpreter to backtrack to an earlier processor state and try
something else at that point. In particular, the main choice that
gives rise to backtracking in PLNR is the set of patterns that come
from the associative memory retrievals of the THGOAL primitive. It is
alleged that the memory and processing cost of backtracking for the
sake of sequencing thru a list of possible associative memory
bindings is less than the cost of programming such searchs explicitly
in the forward direction, say by giving the user set operations.
(...THOR and THAMONG are two other primitives that leave alternatives
in their nodes).
The gross structure of PLNR is quite simple; there are over
100 LISP functions; 1/3 of which are FEXPRS corresponding to the PLNR
primitives; 1/3 of which are success and fail functions for the 16
kinds of PLNR tree nodes; and the last third of which comprise the
associative memory routines, the interpreter and a handful of
miscellaneous subroutines.
(...LISP control in PLNR, starts with a call to THINIT, which
calls THERT; which listens to the user type a PLNR primitive
statement; and then THERT calls THVAL; and THVAL applies LISP's EVAL
to the user's PLNR statement; the PLNR statement gets executed and
changes PLNR memory structures and PLNR control structures as side
effects to THVAL's LISP environment; In particular, PLNR primitives
push nodes into THTREE. Then the PLNR statement returns a LISP value
which is SETQ'ed by THVAL into the variable THVALUE to become the
PLNR value. After a typical successful primitive execution, THVAL
saves THTREE into a variable called THBRANCH, and calls the success
function corresponding to the node that the primitive statement left
on THTREE. The typical success function lops THTREE, and returns
THVALUE untouched. Since the tree is now empty, THVAL returns THVALUE
to THERT which prints it and loops. Complexity arises since
primitives such as THPROG push THBRANCHs into their nodes and cause
THVAL to iterate; and when a PLNR primitive fails, there is usually
going to be a THPROG node someplace above it in the THTREE which will
cause the THVAL to restart the execution at an earlier point but with
some variable set to an alternate value.)
CONTROL STRUCTURE - PROGRAMS & STEPS. PAGE 19
The general appearance of PLNR is similar to that of LISP.
However unlike LISP, in PLNR the prog like control structure
dominates and recursion is secondary. A PLNR program is a list of
steps; a PLNR step is a LISP expression; a step that evaluates to NIL
is said to fail and a step that does not evaluate to NIL is said to
succeed. It is known only to God and Sussman why PLNR failure
should be on the atom NIL rather than on an atom named THNIL; the
reader is encouraged to adopt "NIL FAILS" as his mantra for
meditation on backtracking. (...Use (THDO(THSET X NIL)) and (THSETQ
(THV X)NIL T T) to set a LISP or PLNR variable to NIL without
failing.)
A PLNR program is stored in LISP S-expr in one of four ways;
either as a THPROG, or as a THFIND, or as a theorem body, or as a
THMESSAGE. All four forms of PLNR programs are executed in the same
way so everything that is said below about thPROG execution applies
to theorem bodies, thFINDs and thMESSAGES as well.
Now I would like to define some stack and hardware notions in
terms of a LISP environment. To push a node into a stack means (SETQ
STACK (CONS NODE STACK)); to pop a node off a stack means (PROG2 0
(CAR STACK)(SETQ STACK (CDR STACK))); the terms "stack", "pdl" and
"push down list" refer to list structure that is mostly accessed from
one end. To lop a node off a list, like say to lop the second node
off a list means something like (PROG2 0 (CADR L)(RPLACD L (CDDR
L))). PC means "program counter", SA means "starting address" and
refer to specific positions in a list of executable PLNR steps.
Programs written in PLNR can not be compiled, but rather are
interpreted. The PLNR program interpreter is implemented by seven
LISP functions named THVAL, THPROG, THPROGT, THPROGF, THBRANCH,
THBRANCHUN and THPROGA. Notice that the term "thprog" is overworked;
a lower case thprog refers to a PLNR program; an upper-case THPROG
refers to the subroutine written in LISP that helps to execute
thprogs; and finally there are thPROG tree nodes. But returning to
the parts of the interpreter, THPROG initializes a PLNR program; and
THVAL and THPROGA do most of the work being executed once for each
step of a thprog; THPROGT and THPROGF are trivail auxillarys calling
THBRANCH and THBRANCHUN respectively, which push or pop the PLNR
process state. In its turn, a whole thprog is considered to be a
step that can be included in another thprog.
CONTROL STRUCTURE - PLNR PROCESSOR STATE. PAGE 20
The state of the PLNR processor is contained in seven LISP
variables named THE, THEXP, THVALUE, THTREE, THALIST, THBRANCH and
THABRANCH. THE contains the current step being processed; THEXP
contains the next step to be processed; THVALUE contains the result
of LISP evaluation of a step; THTREE contains a history of past
processor states; THALIST contains a pointer to a variable bindings
push down list; and THBRANCH and THABRANCH are temporaries used for
momentarily holding the THTREE and THALIST when the interpreter is
advancing a step in a program execution.
THE current step.
THEXP next step.
THVALUE result of current step.
THTREE THBRANCH processor states history.
THALIST THABRANCH list of varaibles bindings.
The processor state is saved and restored from a three
element list of the form (THTREE THALIST PC); THTREE and THALIST are
explained below and the PC or "program counter" is a pointer to a
step in a thprog. Such processor states, PS, get saved after each
step execution in a processor state list, PSL, which in turn gets
saved in THPROG tree nodes; all or parts of this processor history
data structure is what are refered to by such anthropomorphisms as
"decisions", "paths", "proof" and so on.
THALIST is a pushdown list of variable bindings; each element
of the THALIST is of the form (varname value) or (varname value
filters); the latter form has to do with the THRESTRICT kludge. A
varname which appears in the THALIST is said to be "BOUND" and must
have a corresponding value; however that value might be the
particular atom named THUNASSIGNED which is provided by the PLNR
varlist binding as a default value. Be sure to distinguish the terms
UNBOUND and UNASSIGNED; UNBOUND means PLNR never heard of that
varname; whereas UNASSIGNED means the varname was declared but a
fetch came before a store.
(...well there's really 10 or 20 more LISP variables having
to do with the processor state. THLEVEL is a pushdown list of (THTREE
THALIST) pairs so that THVAL may be called recursively. LEVEL# is a
count of depth of THVAL recursive calls. THINF is the infinite
failure flag. THOLIST is a pointer to an earlier point in the
THALIST; for example to the state of the THALIST before a pattern
match or theorem varlist binding; THMESSAGE is a flag involved in
thMESSAGE failure propagation. THV is a list with the value (THV
THNV) or (THV) influencing the handling of THV and THNV variables.
THXX is an error message temporary. THTRACE is a trace debugging mode
flag; and finally ↑A,THSTEP,THSTEPD,THSTEPT,THSTEPF are somebody's
idea for single stepping the PLNR interpreter; or for executing stuff
between the cracks in a PLNR interpretation.)
CONTROL STRUCTURE - THTREE. PAGE 21
THTREE is a push down list of tree-nodes; there are 16 kinds
of tree-nodes and each tree-node is a list of two, three or four
elements; the first element of a tree-node list indicates what kind
of node is involved and the remaining elements are data structures
resulting from a computation associated with that kind of node.
The only important and complex PLNR computations are THGOAL
and THPROG; a THGOAL computation searchss the associative data
structure of assertions and theorems and finds a list of potential
pattern matches which is stored in a THGOAL node; a THPROG
computation compounds PLNR statements (like blocks do in ALGOL) and
accumulates a list of processor states, PSL, in its THPROG node.
Schema of a TREE-NODE with accessing functions relative to THTREE:
CAAR CADAR CADDAR CADDDAR
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[ kind tmp1 tmp2 tmp3 ]
↑ ↑ ↑ ↑
CAR CDAR CDDAR CDDDAR
SIXTEEN KINDS OF TREE-NODES
Value-Do Tree-Nodes
1. [THMUNG thml]
2. [THREMBIND tholist]
3. [THDO pc branches abranches]
4. [THUNDO pc branches abranches]
Associative Memory Tree-Nodes
5. [THASSERT pattern property]
6. [THERASE pattern property]
7. [THGOAL pattern-key pattern-hits]
8. [THFIND mode-triple (count . results) macro]
Program Tree-Nodes
9. [THPROG pc psl sa]
10. [THFAIL? prd act]
11. [THTAG tag]
12. [THMESSAGE tharg]
Boolean Tree-Nodes
13. [THAND pc psl]
14. [THOR exprs ]
15. [THAMONG var exprs]
16. [THCOND pairs psl ]
(I've used square brackets to emphasize tree-nodes;
use parens instead, if you wish)
CONTROL STRUCTURE - THTREE - continued. PAGE 22
Now to detail some of the nodes. A [THMUNG thml] node
contains a mung list, thml, of SETQ, RPLACA, RPLACD and PUTPROP
expressions which when evaluated reset values and property lists of
LISP atoms to earlier states. Mung nodes are pushed in thTREE by the
thSETQ, thPUTPROP, thREMPROP, thPLACA, thRPLACD primitives and by the
pattern variable binding mechanism. Observe that THMUNG nodes store a
complete history of old variable values; this lavish use of memory is
required so that the interpreter can backtrack thru its processor
state history. (Well you see if you could backtrack without using a
lot of memory that would violate the second law of thermodynamics and
the computer while backtracking would make the room cooler and we
would all freeze.)
A [THREMBIND tholist] node contains a pointer to the alist
before newer binding (varname value) pairs were push'ed into it.
[THDO pc branches abranches] contains a list of TREEs and ALISTs
called branches and abranches respectively while it goes down its
list of things to be done with its PC; when done THDO changes itself
into a THUNDO and always succeeds.
The THASSERT node and the THERASE node are pushed on the tree
by the THASSERT primitive and the THERASE primitive; assert and erase
are exact inverses of each other and THASSERTs are done to backup
THERASEs and THERASEs are done to backup THASSERTs. The THGOAL node,
as mentioned above, contains the patterns found by an associative
memory search. Notice that searching the associative memory for
assertion and theorem patterns is one thing and using a pattern by
binding it down and calling its theorem is another thing; the first
thing is called a "pattern-accessing" and the second thing is called
a "pattern-binding" or a "try". The point of the backtrack mechanism
is so that the pattern-hits list of THGOAL nodes can be lop'ed thru
and a new pattern "tried".
CONTROL STRUCTURE - THTREE - continued. PAGE 23
The [THPROG pc psl sa] node contains the current state of the
execution of a thprog. The thPROG program counter is a pointer to the
current step being executed; which is the same thing as a list of all
the remaining steps of the thPROG. The sa is a pointer to the first
step of thPROG, which is the same thing as a list of all the steps of
the prog; the sa is only used when a tag must be found. Finally there
is the processor state list, which as mentioned above is a list of
processor states where each processor state is a list of three
elements (thTREE thALIST pc); the particular thTREEs that are getting
pushed into a particular thPROG's processor state list, PSL, are
larger than the THTREE of the thprog; that is the THPROG asks that
one of its steps should be executed; and say that that step pushes
one node into the tree; this new tree is then saved in THBRANCH and
then the success function corresponding to that step's tree node is
executed which pops the tree back to the thprog node; and the thprog
success function takes the THBRANCH and pushes it on its psl and sets
THBRANCH to NIL.
(...this paragraph, trys to explain why whole trees rather
than nodes are pushed into a THPROG node; ...so what is in the psl
are whole trees, when all that really changes between two thprog
steps is that one new node; well you could have just pushed that one
new node into your PSL by CAR'ing it off THTREE and CONS'ing it into
the PSL; but then on a thprog step failure you are agoin' to have to
CONS that very same node to that very same tree which you earlier
CAR'ed it off of; and what is more, when a THSUCCESS or THFAIL is
called the THTREE will be lop'ed quite a few nodes and you would be
required to CAR them off and save them and latter CONS them all back.
Thus the answer to the question of why does the tree point at itself
in such incestously obscene and unPRINTable ways; is that the
implementers wanted to avoid a series of matched POP and PUSH pairs.)
CONTROL STRUCTURE - THE PLNR INTERPRETER. PAGE 24
The PLNR interpreter consists of roughly three cycles;
there's an instruction fetch cycle done by THPROGA or THERT; and
there is an instruction execution cycle done in THVAL; and there is a
conditional branch on success or failure cycle also done in THVAL.
But first consider my impression of THVAL:
α THVAL STEP EXECUTION.
L1: THE ← THEXP;
THEXP ← NIL;
THVALUE ← EVAL(THE);
α THVAL STEP CHAINING MECHANISM.
L2: IF THEXP THEN GO L1;
α SAVE CURRENT PROCESSOR STATE.
IF NULL(THBRANCH) THEN
(THBRANCH ← THTREE; THABRANCH ← THALIST);
α THVAL SUCCESS-FAILURE PROPAGATION.
THEXP ← (get the success or failure function
corresponding to the kind of node that
is at the top of thTREE);
THVALUE ← ((PROG2 0 THEXP (SETQ THEXP NIL)));
GO L2;
THVAL consists of four parts; starting at the top, assume
that somehow a lisp expression, possibly a PLNR FEXPR primitive, is
in THEXP; so the interpreter takes the next statement to be executed
from THEXP and makes it the current statement to be executed into THE
and clears THEXP; and EVAL's THE. Now if the evaluation of that
statement had the side affect of putting something new in THEXP then
the interpreter chains another execution cycle onto the previous one
and the success or failure of that earlier execution cycle is
irrelevant; further notice that if a function wishs to be transparent
to the PLNR THVALUE then it must return THVALUE as its LISP value.
After executing a step and all the steps chained to that
step; the interpreter finds NIL in THEXP and falls thru the chaining
mechanism, and usually decides to save the THTREE and THALIST in
THBRANCH and THABRANCH for the benefit of THPROG and THANDS which
snarf the branches into their nodes; then the interpreter enters the
success-failure propagator which is merely a jump table keyed by
THVALUE and the kind of node in the top of THTREE; NIL in THVALUE
selects failure, non-NIL in THVAL selects success. Then the success
or failure tree node function is executed in such a fashion that
THEXP is again chainable without using THE, (observe the double
parens around that PROG2 and think about it). Most of the tree node
functions merely POP the tree and are transparent to THVALUE; the two
important tree node functions are THGOALF which gets a new try out of
its node and succeeds thus stopping a failure propagation; and
THPROGT which gets the next sequential steps from some thprog until
stopped by a step failure.
CONTROL STRUCTURE - THE PLNR INTERPRETER - continued. PAGE 25
Success-Failure Propagation, SFP.
The terms "success-propagation" and "failure-propagation"
refer to THVAL's second loop (shown on the previous page) which
rather than executing steps from a thprog, is actually executing
nodes from the tree. A success-propagation is selected by THVALUE
non-NIL and a failure-propagation is selected by THVALUE NIL. In a
typical propagation cycle the top node in the tree is used as a key
into the SFP jump table which contains sixteen success functions and
sixteen failure functions. A typical failure SFP function executes
the top node of the tree, which undoes something that some thprog
step once did; then the failure function pops the tree and returns
NIL. On the other hand a typical success SFP function just pops the
tree and returns THVALUE so as to be THVALUE transparent. Failure
propagation continues until stopped by a THGOAL node which has some
trys left; success propagation continues until stopped by a THPROG
node that has some steps left.
In a sense, "larger" success-propagation and
failure-propagation are provided in PLNR by the primitives THFAIL,
THSUCCEED, THMESSAGE and THFINALIZE which have SFP loops similair to
THVAL's but with a different escape criterion; usually these
primitive are looking for a particular kind of node or a tag in the
tree to terminate their propagation. These four primitives provide
for all PLNR's non-theorem control transfers such as jump, return and
err.
A SUMMARY OF THE 35 PLNR PRIMITIVES. PAGE 26
SIX VALUE PRIMITIVES
1. (THVAL expr alist) PLNR's EVAL.
2. (THSETQ var1 e1 ... varn en) undone on failure.
3. (THVSETQ var1 e1 ... varn en) not undoable.
4. (THV varnam) ≡ (THNV varname) returns variable's value.
5. (THASVAL var) assigned value predicate.
6. (THRESTRICT varname filters) restricts pattern binding.
SIX THEOREM PRIMITIVES
1. (THASSERT pattern recommendations...)
(THPSEUDO)(THPROP expr)(THTBF filter)(THUSE thms...)
2. (THERASE pattern recommendations...)
(THPSEUDO) (THTBF filter)(THUSE thms...)
3. (THGOAL pattern recommendations...)
(THNODB)(THDBF filter) (THTBF filter)(THUSE thms...)
4. (THFIND mode macro varlist steps...)
mode= ALL or integer or (lo hi flg)
5. (THDO e1...en)
6. (THAPPLY theorem assertion)
EIGHT PROG PRIMITIVES
1. (THPROG varlist steps...)
2. (THSUCCEED node) or (THSUCCEED THTAG tag)
3. (THFAIL node) or (THFAIL THTAG tag)
4. (THMESSAGE varlist pattern steps...)
5. (THGO tag)
6. (THRETURN expr)
7. (THUNIQUE varnam)
8. (THFINALIZE arg1 arg2)
FIVE BOOL PRIMITIVES FIVE IO PRIMITIVES
1. (THAND e1...en) 1. (THDUMP)
2. (THOR e1...en) 2. (THDATA)
3. (THAMONG varnam expr) 3. (THBKPT comment)
4. (THCOND pair1 pairn) 4. (THERT err-message)
5. (THNOT expr) 5. (UREAD filename)
FIVE LISPISH PRIMITIVES
1. (THPUTPROP name property indicator)
2. (THDEFPROP name property indicator)
3. (THRPLACA destination source)
4. (THRPLACD destination source)
5. (THFLUSH indicators...)
THEOREM FORMATS
(DEFPROP thm(THCONSE varlist pattern-tag steps...)THEOREM)
(DEFPROP thm(THANTE varlist pattern steps...)THEOREM)
(DEFPROP thm(THERASING varlist pattern steps...)THEOREM)
PATTERN FORMAT
pattern ← (itemexprs...) or (THEV expr)
itemexpr ← ? or item or itemvar or listitem or (THEV expr)
or (THRESTRICT itemvar filters) or (THRESTRICT ? filters)
itemvar ← (THV varname) or (THNV varname) or ?varname or ←varname
SIX VALUE PRIMITIVES PAGE 27
1. (THVAL expression alist)
THVAL is the PLNR evaluator just as EVAL is the LISP
evaluator. As in LISP, the expression is evaluated (THVALuated)
with free variables in it given the values associated with them on
the given alist. PLNR's alist, called THALIST, is a list of pairs
(CAR-CADR not CAR-CDR) of variable names and values. The alist
argument is optional and when omitted indicates THVAL'ing under the
current binding. If an error occurs while THVALing an expression, an
error message is printed and THVAL goes into the PLNR listening loop.
To proceed by succeeding, type T; to terminate the calculation by
failure type NIL.
2. (THSETQ var1 expr1 ... varN exprN)
THSETQ sets each variable to the value of the corresponding
expression; Undone if failure backs up to it. If the variable is a
PLNR variable of the form (THV var) or (THNV var) then the
corresponding expression is THVAL'ed; otherwise the expression is
EVAL'ed.
3. (THVSETQ var1 expr1 ... varN exprN)
Sets each variable to the value of the corresponding
expression, as in THSETQ; However THVSETQ's are not undone on failure
backup.
4. (THV varname) ≡ (THNV varname)
As primitives, THV and THNV are identical and return the PLNR
value of the variable named. It is when THV and THNV are used in
patterns that they are different, THV holds sticky to its value and
THNV yields in order to match.
5. (THASVAL variable)
THASVAL is a predicate which assumes that the indicated
variable is bound. It succeeds if and only if the variable is
assigned a value.
6. (THRESTRICT varname filters)
THRESTRICT nconc's the filter functions onto the variables
THALIST pair; only in pattern-binding does the value have to pass
thru its restriction filters.
SIX THEOREM PRIMITIVES PAGE 28
1. (THASSERT pattern recommendations...)
atomic pattern add thm name to theorem base.
non-atomic pattern add assertion to data base.
(THPSEUDO) inhibit memory store operation.
(THPROP expr) store property with assrtn or thm.
(THTBF filter) call THANTE theorems by filtering.
(THUSE thms...) call THANTE theorems by name.
2. (THERASE pattern recommendations...)
atomic pattern remove thm name from theorem base.
non-atomic pattern remove assertion from data base.
(THPSEUDO) inhibit memory erase operation.
(THTBF filter) call THERASING theorems by filtering.
(THUSE thms...) call THERASING theorems by name.
As memory operations on the assertion data base, (THASSERT
pattern) and (THERASE pattern) add or remove an assertion to or from
the data base. The assertion is formed from the pattern by taking the
values of variables and by THVALing THEV expressions; the initial
pattern must not have any unbound or unassigned variables. If the
assertion has already been asserted or erased then the value NIL is
returned indicating failure; else the assertion cons'd to its
property expr is returned indicating success.
As memory operations on the theorem base, (THASSERT thm) and
(THERASE thm) add or remove the name of a theorem to or from the
theorem base. Theorem names being atomic, are distinguishable from
patterns which are never atomic. Theorems have to be defproped before
they are THASSERT'ed; THASSERTING only looks at the pattern-tag of
the theorem; so theorem bodies can be changed without having to
re-THASSERT them. If a theorem of the same name has already been
asserted or erased then the value NIL is returned indicating failure;
else the name of the theorem is returned indicating success. THASSERT
will interpret the THPROP recommendation `expr' as a property list of
indicator value pairs to be putprop'ed on the theorem name.
As control operations, THASSERT and THERASE are alike in
being able to call subroutines by pattern; that is THASSERT can call
THANTE theorems and THERASE can call THERASING theorems. The theorems
to be called must either be explicitly named in a (THUSE thms...)
recommendation or implicity specified by a (THTBF filter)
recommendation. The (THTBF THTRUE) recommendation will call all
theorems with patterns corresponding to the calling pattern key. The
(THPSEUDO) recommendation enables theorem calling by pattern to be
done independent of memory operations; (...and so defeating the
`unified PLANNER' memory-control theory; since pseudo erasing
theorems and pseudo antecedant theorems are only different in name
alone). All the theorems that are recommended and match-accessed and
get thru the filters and thru the match-binding are executed for
side-effect, their values are ignored.
SIX THEOREM PRIMITIVES - continued. PAGE 29
3. (THGOAL pattern recommendations...)
(THNODB) no data base search.
(THDBF filter) recommend a data base filter.
(THTBF filter) recommend a theorem base filter.
(THUSE thms...) call THCONSE theorems by name.
THGOAL searches the data base for an assertion which matches
the pattern. If it finds one, it succeeds after assigning all of
the unassigned variables in the pattern so as to make it match the
assertion; it then returns the assertion found as its PLNR value. If
it does not find a matching assertion it fails. If after a success,
a failure propagates back to it, it unassigns the variables it
assigned last time and continues its search for a matching assertion
from where it left off.
If recommendations are given they are tried in order. If the
very first recommendation is a (THNODB) then the data base search is
inhibited. The possible recommendations are: (THNODB) - Inhibit data
base search. (THDBF filter) - Try only those assertions of the data
base satisfying the given assertion filter. (THTBF filter) - Try only
those theorems satisfying the given theorem filter. (THUSE thms...) -
Try the THCONSE theorems given explicitly by their names in the order
mentioned.
If the THCONSE theorem succeeds, the PLNR value of the THGOAL
will be the pattern of the goal with the assignments substituted for
the assigned variables, unless the theorem does a THRETURN, in which
case the PLNR value of the THGOAL will be the expression returned. If
a goal variable which is unassigned is matched against a theorem
variable and the theorem eventually gives that variable a value then
the goal variable also gets that value. (...this is what is called
bind-by-name in part I.)
SIX THEOREM PRIMITIVES - continued. PAGE 30
4. (THFIND mode macro varlist step1...stepN)
THFIND is a primitive whose THVALuation yields a list of
objects, each of which is the result of substituting for variables in
the macro those combinations of variables which cause the program
starting at the varlist (like a THPROG) to succeed.
THFIND example:
the data-base contains the assertions
(HACKER N) ; Nelson is a Hacker
(HACKER H) ; Holloway is a Hacker
(HACKER RG) ; Greenblat is a Hacker
(AT MAC RG) ; Greenblat is at MAC
and we THVALed the expression
(THFIND ALL (AT SC (THV X)) (X)
(THGOAL (HACKER (THV X)))
(THNOT(THGOAL (AT MAC (THV X)))))
we would get PLNR value THVALUE:
((AT SC N) (AT SC H))
The mode field of a THFIND statement is a triplet (min max
result). THFIND fails unless it finds at least a number equal to
CAR of the mode and if it finds greater than or equal to CADR of the
mode it returns CADDR of the mode. If CADR of the mode is not a
number it will never be found. The mode triplet may be abbreviated
by ALL = (1 NIL NIL), any number n = (n n T).
5. (THDO expr1 ... exprN)
THDO executes each of its subexpressions in turn and cares
not whether they succeed or fail; it then succeeds. If a failure
backs up to it, all that it did is undone. (THDO(SETQ X NIL)) is one
of the few ways that one can successfully set something to NIL without
failing in the PLNR sense of success and failure.
6. (THAPPLY theorem assertion)
THAPPLY calls the specified theorem causing it to match its
pattern to the specified assertion. If it matches the theorem is
executed with assertion as its "argument." The THVALUE of a THAPPLY
is the value of the theorem applied.
EIGHT PROG PRIMITIVES PAGE 31
1. (THPROG varlist steps...)
OUTLINE OF THPROG EXECUTION:
i. Bind Varlist.
ii. Execute steps in Sequence.
iii. Atomic steps are tags, (THGO tag) alters the sequence.
THPROG is the PLNR analog of the LISP function PROG. THPROG
binds the variables mentioned in its varlist and then executes the
steps in sequence, unless changes in sequence are specified by tags
and THGO statements. As in LISP, atoms occuring in THPROG bodies are
interpreted as tags and (THGO tag) causes execution to proceed from
the expression immediately following the tag. THGO statements may
refer to tags which are in thprogs containing the current thprog.
THPROG may be terminated by (THRETURN expr) which is
equivalent to (THSUCCEED THPROG exp) and will cause the THPROG to
succeed and return as its PLNR value the LISP value of the indicated
expression. If a THPROG terminates by succeeding past its last
statement, or by executing a (THSUCCEED THPROG), THNOVAL is returned
as the THPROG PLNR value. If the THPROG fails, it returns NIL.
An element of the varlist may be either an atom which is the
name of a variable to be used inside the THPROG, or a list of two
elements, the first of which is the variable name and the second of
which is a LISP expression whose LISP value is to be used as the
initial value of the variable. If a variable is bound without giving
it an initial value it is given the default value "THUNASSIGNED."
Interpretation of a THPROG begins at the first step of the
indicated sequence. If it succeeds, a new branch is generated on
THTREE and the next step in sequence is evaluated. If any step fails
then the branches are unwound until either a new success ends the
failure propagation or there are no more branches and the THPROG
fails. Thus THPROG behaves as a THAND with variable binding
capability; it fails unless each of its steps succeeds, allowing for
backup, until it returns. As usual, any LISP expression may appear
in a THPROG; if it evaluates to NIL, a failure is generated,
otherwise a success is assumed.
EIGHT PROG PRIMITIVES - continued. PAGE 32
Following Rudyard Kipling, PLNR meets with success and
failure and treats those two imposters much the same. On both success
and failure the THTREE is popped until an earlier node is found from
which execution can be continued; also both success and failure
replace the word THEOREM with the word THPROG (...so contrary to
innocent expectations, success theorem will not get you out of a
theorem that's a couple of thprogs deep).
2. (THSUCCEED node expr)
THSUCCEED causes success to propagate to a node or tag.
(THSUCCEED THTAG tag) ≡ (THGO tag)
(THSUCCEED THPROG e) ≡ (THRETURN e)
(THSUCCEED place) ≡ (THSUCCEED place T)
(THSUCCEED THEOREM expr) ≡ (THSUCCEED THPROG expr)
(THSUCCEED THEOREM) ≡ (THSUCCEED THPROG)
(THSUCCEED) ≡ PLNR no operation.
3. (THFAIL node expr flag)
THFAIL causes failure to propagate to a node or tag. THFAIL
finds the specified target node and it splices a THFAIL? node into
the tree at that point and then it returns a NIL. THFAIL THINF and
THFAIL MESSAGE are handled as special cases and resemble "real"
THFAIL in name alone.
(THFAIL THTAG tag T) causes a failure to go to the tag.
(THFAIL THTAG tag) causes a failure to go past the tag.
(THFAIL THPROG) causes the THPROG to fail.
(THFAIL THEOREM) causes the THEOREM to fail.
(THFAIL THINF) causes failure to top level of THVAL.
(THFAIL THMESSAGE message) causes a failure to propagate
until it reaches a THMESSAGE statement whose pattern matches the
message.
4. (THMESSAGE varlist pattern steps...)
Examines failures propagating to it, if one has a message which
matches the pattern (after the varlist is bound) then control is
passed to the body which executes as a THPROG.
5. (THGO tag) ≡ (THSUCCEED THTAG tag)
6. (THRETURN expr) ≡ (THSUCCEED THPROG expr)
EIGHT PROG PRIMITIVES - continued. PAGE 33
7. (THUNIQUE varname)
THUNIQUE is a primitive by which a user may test to see if he
is in one kind of infinite loop. THUNIQUE assumes that the variable
given is bound. If the variable is bound, it is assumed that it is
assigned to a list of atoms and expressions. THUNIQUE will then fail
if there is any previous binding and assignment of the given variable
for which the atoms and expressions THVALuate identically, the atoms
being interpreted as variables.
8. (THFINALIZE node) or (THFINALIZE THTAG tag)
THFINALIZE is a primitive which allows pruning of THTREE.
Essentially, if one THFINALIZES, say to a tag, then all the things
done since that tag was passed are not undoable in case of failure.
Besides finalizing to a tag, one can finalize a theorem or a THPROG
by saying (THFINALIZE THEOREM) or (THFINALIZE THPROG).
Example: To put all of the green blocks in the box and return a list
of those actually moved:
(THPROG (X (Y NIL))
(THOR (THAND (THGOAL (IS (THV X) BLOCK))
(THGOAL (COLOR (THV X) GREEN)))
(THRETURN (THV Y)))
FOO (THCOND ((THGOAL (CONTAIN BOX (THV X))) (THFAIL))
((THGOAL (PUTIN (THV X) BOX) (THUSE TC-PUTIN))
(THSETQ (THV Y) (CONS (THV X) (THV Y)))
(THFINALIZE THTAG FOO)
(THFAIL))
((PRINT (THV X)) (THERT CAN NOT PUT IT IN)) )
)
FIVE BOOL PRIMITIVES PAGE 34
1. (THAND expr1...exprN)
THAND fails unless each of its expressions succeeds. It is
just like THPROG except that there are no variable declarations or
tags.
2. (THOR expr1...exprN)
THOR succeeds if at least one of its subexpressions succeeds.
Basically, it CDRs down the list looking for a winner and if it finds
one it succeeds, returning its value as the PLNR value. If a
failure propagates back to it, however, it continues CDRing from the
point it left off until it finds another winner or it loses.
3. (THAMONG varname expression)
Upon entry the variable named must be bound. If
it is unassigned then it will be assigned to the first member of the
list of choices to which expression THVALuates. If the variable
already has a value (is assigned), THAMONG fails unless the assigned
value is already among the choices. Each time a failure backs up to
the THAMONG the variable will be assigned to the next element of the
choice list. If it runs out of choices it fails, otherwise it
succeeds.
4. (THCOND pairs...)
THCOND is the PLNR analog of COND in LISP. As in Stanford
LISP the "pairs" needn't be. Basically THCOND executes the CAR of
each pair until one succeeds. The THCOND will then succeed if all
the rest of that "pair" succeeds (like a THAND) else THCOND will
fail. THCOND is an abbreviation for the structure:
(THOR (THAND expr(THAND exprs...))...)
5. (THNOT expr) ≡ (THOR (THAND expr (THFAIL))(THSUCCEED)).
FOUR IO PRIMITIVES PAGE 35
1. (THDUMP) dumps all the PLNR assertions and theorems on the
currently selected output devices.
2. (THDATA) causes PLNR to go into a read loop for inputing
assertions and theorems. THDATA is the inverse of THDUMP.
3. (THBKPT comment) has no effect unless THTRACE is set non-NIL. If
it is, a THBKPT becomes a comment which is typed out and which breaks
if desired.
4. (THERT error-message) types out the error message and waits for
the user to type T or NIL to indicate whether to continue with
statements following THERT or whether to backup by FAIL'ing at THERT.
THERT's listen loop is the one and only listen loop in PLNR.
5. (UREAD filename) Reads a DSK: file and executes all the
statements at PLNR level, ignores commentary delimited by the atoms
COMMENT and semicolon.
FIVE LISPISH PRIMITIVES
THPUTPROP, THREMPROP, THRPLACA, THRPLACD are like their LISP
counterparts except that if a failure backs up to them they undo
their effect.
(THFLUSH indicator1 indicator2 ...)
THFLUSH remprop's all properties with the indicators specified from
all atoms on the OBLIST. For example (THFLUSH SUBR FSUBR) will
lobotomize PLNR and the LISP in which it is embedded.
(SETQ MONKEY @(THGOAL (MONKEY GETS BANANAS)(THTBF THTRUE))) PAGE 36
(THASSERT(CLIMBABLE BOX))
(THASSERT(BOX AT A))
(THASSERT(MONKEY AT B))
(THASSERT(BANANAS AT C))
(THASSERT(MONKEY OFF BOX))
(DEFPROP REACH (THCONSE (XYZ) (MONKEY GETS BANANAS)
(THASSERT (MONKEY WANTS BANANAS))
(PRINT @(THE MONKEY THINKS HE WANTS SOME BANANAS))
(THOR
(THGOAL (BANANAS AT (THV XYZ)))
(THFAIL THEOREM @(YES, WE HAVE NO BANANAS)) )
(THASSERT (MONKEY AT (THV XYZ))(THPSEUDO)(THTBF THTRUE))
(THOR
(THAND
(THGOAL (MONKEY AT (THV XYZ)))
(THGOAL (MONKEY ON BOX)) )
(THFAIL THEOREM @(MONKEY DIDN'T MOVE, MONKEY NOT WELL)))
(THERASE (MONKEY WANTS BANANAS))
(PRINT @(MONKEY GETS BANANAS))
(THSUCCEED THEOREM @SUCCESS)
)THEOREM)
(THASSERT REACH)
(DEFPROP MOVEBOX (THANTE (X Z Q) (BOX AT (THV X))
(THGOAL (BOX AT (THV Z)))
(THOR
(THAND (EQUAL (THV X)(THV Z))
(THSUCCEED THEOREM))
T)
(THGOAL (MONKEY AT (THV Q)))
(THOR (THOR
(THGOAL (MONKEY OFF BOX))
(THAND
(THNOT (THGOAL (MONKEY ON BOX)))
(THASSERT (MONKEY OFF BOX))) )
(THAND
(THERASE (MONKEY ON BOX))
(THASSERT (MONKEY OFF BOX))
(PRINT @(MONKEY NOTICES HE IS ON THE BOX))
(PRINT @(MONKEY GETS OFF THE BOX))) )
(THOR (EQUAL (THV Q)(THV Z))
(THASSERT(MONKEY AT(THV Z))(THPSEUDO)(THTBF THTRUE)))
(THERASE (BOX AT (THV Z)))
(THASSERT (BOX AT (THV X)))
(THERASE (MONKEY AT (THV Z)))
(THASSERT (MONKEY AT (THV X)))
(PRINT (LIST @MONKEY @MOVES @BOX @FROM (THV Z) @TO (THV X)))
(THSUCCEED THEOREM)
)THEOREM)
(THASSERT MOVEBOX)
(DEFPROP CLIMB (THANTE (X Y Z W S Q) (MONKEY AT (THV X)) PAGE 37
(THGOAL (MONKEY AT (THV Q)))
(PRINT (LIST @MONKEY @IS @AT (THV Q)))
(THCOND ((THGOAL (MONKEY WANTS (THV Y))) (THGO B))(T T))
A (THAND (THOR
(THGOAL (MONKEY OFF BOX))
(THAND
(THERASE (MONKEY ON BOX))
(THASSERT (MONKEY OFF BOX))
(PRINT @(MONKEY NOTICES HE IS ON THE BOX))
(PRINT @(MONKEY CLIMBS OFF THE BOX))) )
(THOR
(THGOAL (MONKEY AT (THV X)))
(THAND
(THERASE (MONKEY AT (THV Q)))
(THASSERT (MONKEY AT (THV X)))
(PRINT(LIST @MONKEY @GOES @FROM(THV Q)@TO(THV X)))))
(THSUCCEED THEOREM @SUCCESS))
(THFAIL THEOREM (PRINT @(WHAT MONKEY ?)))
B (PRINT (LIST @THE @MONKEY @WANTS @SOME (THV Y)))
(THGOAL ((THV Y) AT (THV S)))
(PRINT (LIST @MONKEY @NOTICES @THAT (THV Y) @ARE @AT (THV S)))
(THOR (EQUAL (THV X)(THV S))
(THGO A) )
(THOR
(THAND
(THGOAL ((THV W) AT (THV Z)))
(THGOAL (CLIMBABLE (THV W)))
(PRINT (LIST @MONKEY @NOTICES @A (THV W) @AT (THV Z))) )
(THFAIL THEOREM
(PRINT @(ALONE IN THE WORLD, WITH OUT A FRIEND))) )
(THOR
(EQUAL (THV Z) (THV S))
(THASSERT ((THV W) AT (THV S))(THPSEUDO)(THTBF THTRUE)))
(THOR
(THGOAL (MONKEY AT (THV S)))
(THAND
(THERASE (MONKEY AT (THV Q)))
(THASSERT (MONKEY AT (THV S)))
(PRINT (LIST @MONKEY @GOES @FROM (THV Q) @TO (THV S)))) )
(THAND
(THOR
(THERASE (MONKEY OFF (THV W)))
T)
(THOR
(THAND
(THASSERT (MONKEY ON (THV W)))
(PRINT (LIST @MONKEY @CLIMBS @ON (THV W))) )
(PRINT @(MONKEY ALREADY ON BOX, BUT YOU KNEW THAT))) )
(THSUCCEED THEOREM)
)THEOREM)
(THASSERT CLIMB)
PLNR ERROR MESSAGES explanation PAGE 38
expr LISPERROR - THVAL LISP error when evaluating the expr.
BAD SUCCEED - THVAL PLNR interpreter bug.
BAD FAIL - THVAL PLNR interpreter bug.
expr UNCLEAR RECOMMENDATION - THTRY
THGOAL recommendation expr not one of
the following four recommendations
THNODB, THDBF, THTBF, THUSE.
expr UNCLEAR RECOMMENDATION - THTAE
THASSERT or THERASE recommendation expr
not one of the following four
THPSEUDO, THPROP, THTBF, THUSE.
name BAD THEOREM - THTRY1 Name lacks a THCONSE theorem.
name BAD THEOREM - THTAE Name lacks a THERASING or THANTE theorem.
varname THUNBOUND - THV1 Variable wasn't declared.
varname THUNBOUND - THGAL Variable wasn't declared.
varname THUNASSIGNED - THV1 Fetch varname came before any stores.
expr NOT FOUND - THUNIQUE
BAD CALL - THFINALIZE Finalize argument missing.
node OVERPOP - THFINALIZE Finalize target node not found.
node OVERPOP - THSUCCEED Succees target node not found.
node OVERPOP - THFAIL Failure target node not found.
OVERPOP - THREMBIND PLNR bug.
ODD NUMBER OF GOODIES - THSETQ odd argument list length.
ODD NUMBER OF GOODIES - THVSETQ odd argument list length.
IMPURE ASSERTION OR ERASURE - THASS1
Unassigned variable in assertion.
GLOSSARY and INDEX PAGE 39
antecedent......................THCONSE theorem's pattern-tag.
assertion.......................page 4.
assigned........................bound variable value not THUNASSIGNED.
bind-by-value...................variable assigned constant.
bind-by-name....................theorem variable linked to variable.
bound...........................variable is on THALIST.
consequent......................THCONSE's pattern-tag.
calling-pattern-key.............page 8.
car cadr cdr cons...............see LISP manual
datum...........................olde PLANNER word for assertion.
defprop putprop remprop.........see LISP manual
expr............................expression.
filter..........................page 11
goal............................page 10
item............................an atomic pattern element.
itemvar.........................page 7, a (THV x) or (THNV x).
lop.............................(PROG2 0(CAR L)(SETQ L(CDR L)))
mapc............................see LISP manual
nconc...........................see LISP manual
pattern.........................page 7.
pattern-bind....................page 12, comparisons and assignments.
pattern-access..................page 12, an associative memory search.
pattern-match...................page 12, to access and bind.
rplaca rplacd ..................see LISP manual
skeleton........................olde PLANNER word for pattern.
snarf...........................fetch value from var and clear var.
theorem.........................page 9, theorems are subroutines.
theorem-pattern-tag.............page 8.
try.............................a THCONSE theorem call.
unassigned......................bound variable value is THUNASSIGNED.
unbound.........................variable is not on THALIST.
varlist.........................page 11.
varname.........................atomic variable name.